package leetCode.offer41;


public class MediaFinder2 implements MediaFinder{

    Node root;
    int length;

    @Override
    public void addNum(int num) {
        root = insert(root,num);
        length++;
    }

    @Override
    public double findMedian() {
        int[] result = new int[1];
        if(length%2==0){
            mSearch(root,length/2+1,result);
            int one = result[0];
            mSearch(root,length/2,result);
            return (double) (one+result[0])/2;
        }else{
            mSearch(root,length/2+1,result);
        }
        return result[0];
    }

    /**
     *  插入元素
     *  基本思想是顺着树往下走，将其插入合适的位置，
     *  找个图，对着这个过程走一遍即可理解, 此树很明显不能存储相同值的节点
     * @param root 根节点
     * @param data
     * @return
     */
    Node insert(Node root ,int data) {
        // 这一步很简单，就是root为空去情况
        if(root == null) {
            int[] datas = new int[1];
            datas[0] = data;
            root = new Node(datas);
        } else {
            if(data < root.data[0]){
                root.left = insert(root.left,data);
            } else if(data > root.data[0]) {
                root.right = insert(root.right,data);
            }else{
                int[] newDatas = new int[root.data.length+1];
                System.arraycopy(root.data,0,newDatas,0,root.data.length);
                newDatas[root.data.length] = data;
                root.data = newDatas;
            }
        }
        return root;
    }

    int mSearch(Node root,int index,int[] result) {
        if(root!=null) {
            index =  mSearch(root.left,index,result);
            index = index - root.data.length;
            if(index<=0) {
                result[0] = root.data[0];
                return Integer.MAX_VALUE;
            }
            index = mSearch(root.right,index,result);
        }
        return index;
    }

  static class Node{
        public int[] data;
        public Node left;
        public Node right;

        public Node(int[] data){
            this.data = data;
        }
    }

    public static void main(String[] args) {
        MediaFinder mediaFinder = new MediaFinder2();
        mediaFinder.addNum(6);
        mediaFinder.addNum(10);
        mediaFinder.addNum(2);
        mediaFinder.addNum(6);
        mediaFinder.addNum(5);
        System.out.println(mediaFinder.findMedian());
    }

}
